//https://www.luogu.com.cn/problem/P1168
#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
using namespace std;


vector<int> do_midium(const vector<int>& v){
	size_t sz=v.size();
	vector<int> res;
	array<int,5> temp;
	res.push_back(v[0]);
	if(sz<=5){
		for(int i=0;i<sz;++i){
			temp[i]=v[i];
		}
		for(int i=3;i<=sz;i+=2){
			std::sort(temp.begin(),temp.begin()+i);
			res.push_back(v[i/2]);
		}
		return res;
	}
	
	for(int i=0;i<5;++i){temp[i]=v[i];}
	for(int k=3;k <= 5;k += 2) {
		std::sort(temp.begin(), temp.begin() + k );
		res.push_back(temp[k / 2]);
	}
	const auto insert=[&temp](int n){
		if(n<temp[2]){
			temp[4]=n;
			}
		else{
			temp[0]=n;
			}
		std::sort(temp.begin(),temp.end());
	};
	for(int k=5;k<sz;){
		insert(v[k++]);
		insert(v[k++]);
		res.push_back(temp[2]);
	}
	return res;
}

int main(){
	int N;
	cin>>N;
	vector<int> V;
	V.resize(N);
	for(int i=0;i<N;++i){
		cin>>V[i];
	}
	if(N%2==0){
		V.pop_back();
	}
	auto mids=do_midium(V);
	for(int i: mids){
		cout<<i<<'\n';
	}
	return 0;

}
